package Java学习;

import java.util.Random;

public class 快速排序 {
    public static void quclick(int[] arr, int i, int j){
        int start = i;
        int end = j;
        if (start > end){
            return;
        }

        while (start != end){

         while (true){
             if (end<=start||arr[start]>=arr[i]){
                 break;
             }
             start++;
         }
            while (true){
                if (end<=start||arr[end]<=arr[i]){
                    break;
                }
                end--;
            }
            int temp1;
            temp1 = arr[start];
            arr[start] = arr[end];
            arr[end] = temp1;

        }
        int temp2;
        temp2 = arr[start];
        arr[start] = arr[i];
        arr[i] = temp2;
        quclick(arr, i, start-1);
        quclick(arr, start+1, j);
    }
    public static void main(String[] args) {
        Random rm = new Random();
        int[] arr = new int[100000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = rm.nextInt();
        }
        long start = System.currentTimeMillis();
        quclick(arr, 0, arr.length-1);
        long end = System.currentTimeMillis();
        System.out.println(end-start);
//        for (int i = 0; i < arr.length; i++) {
//            System.out.print(arr[i] + " ");
//        }
    }

}
